package easy;

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 示例 1：
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * <p>
 * 示例 2：
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 * <p>
 * 提示：
 * 1 <= strs.length <= 200
 * 0 <= strs[i].length <= 200
 * strs[i] 仅由小写英文字母组成
 * <p>
 * Related Topics 字符串
 * 👍 1766 👎 0
 */
public class L14_最长公共前缀 {
    public static void main(String[] args) {
        String[] strs = new String[]{"aac", "cab", "abb"};
        String res = new L14_最长公共前缀().longestCommonPrefix(strs);
        System.out.println(res);
    }

    /**
     * 先求出最短长度,再进行循环.
     * <p>
     * 执行耗时:1 ms,击败了75.69% 的Java用户
     * 内存消耗:36.1 MB,击败了98.23% 的Java用户
     */
    public String longestCommonPrefix(String[] strs) {
        int minLen = 201; // end指针为最小长度的字符串.
        for (String str : strs) {
            if (str.length() < minLen)
                minLen = str.length();
        }

        int end = minLen;
        String mark = strs[0]; // 基准值
        for (int i = minLen - 1; i >= 0; i--) {
            for (int j = 1; j < strs.length; j++) {
                Character tmp = mark.charAt(i);
                if (strs[j].charAt(i) != tmp) {
                    end = i;
                    break;
                }
            }

        }

        return mark.substring(0, end);
    }
}
